\documentclass[10pt,A4]{report}
\usepackage[utf8x]{inputenc} 
\usepackage[russian]{babel}
\usepackage{amsmath, amssymb}
\usepackage{amsfonts, makeidx}
\usepackage{graphicx}

\footskip  1.cm \evensidemargin 0.25cm \textwidth 11.5cm
\textheight 16.7cm \topmargin -1.8cm


\newcounter{chap}

\newcommand{\mychap}[1]{
\newpage

\addcontentsline{toc}{section}{#1}

{\refstepcounter{chap} {\bf \Huge #1}
}
}

\evensidemargin -1in
\oddsidemargin -1in
\evensidemargin 0cm
\oddsidemargin 0cm
\textwidth 17cm
\textheight 25cm

\begin{document}

\Large

\mychap{Введение}

Булева алгебра - это тот раздел математики, который интенсивно используется на сегодняшний день. Элементы ее можно встретить в помехоустойчивом кодировании, криптографии, построении электронных схем. А это именно те отрасли, которые воочию работают в любом электронно-цифровом устройстве.

Функции можно представлять двумя способами: термальным и векторным. Векторная запись (или табличная) функции является однозначной. Если имеется $f(x_1, x_2, \ldots, x_n)$, то вектор, представляющий эту функцию, будет единственным и иметь длину $2^n$. С термальными представлениями булевых, как и любых других функций дела обстоят не так просто.

Во-первых, термальных представлений одной и той же функции может быть бесконечно много. Для многих задач
для функции необходимо использовать наиболее простые термальные представления (это в частности касается
построения электронных схем). Если рассуждать с точки зрения построения электронных схем, то 
под простотой термального представления можно понимать количество операций (транзисторов) в функции. То есть
чем меньше операций в функции, тем меньше будет использоваться транзисторов, в следствии чего уменьшится размер, цена, потребление энергии, выделение тепла и возрастет производительность электронной схемы.

Есть тривиальные алгоритмы, которые дают термальные представления булевых функций, но результат
выполнения в большинстве случаев не дает самых оптимальных результатов  с точки зрения количества используемых операций (СКНФ, СДНФ, СПНФ, полиномы Жегалкина). Так же, эти алгоритмы дают решение с использованием определенных фукнций, правда замыкание  множеств этих функций является полным.

Работа в области минимизации булевых функций была начата нами в 2007 году и продолжается до сих пор. 

\mychap{Содержание работы}

Любую булевую функцию можно записать несколькими способами в термальном представлении.
Если терм состоит только из функций: $x$, $\overline{x}$, $ x \oplus y$ и $ x \cdot y $, то он
называется термом в {\it полиномиальном представлении}.

Очевидно, что для одной и той же функции может быть бесконечное количество полиномиальных представлений. 
Можно выделить класс {\it минимальных полиномиальных представлений}.
Минимальным полиномиальным представлением булевой функций будем называть такое полиномиальное представление, 
в котором количество "$ \oplus $" меньше, либо равно количеству во всех остальных полиномиальных представлениях этой же функции.

Сложность функции $f$ будем обозначать $L(f)$. 

Ниже представлена таблица с унарными функциями и их сложностями.
\begin{center}
\begin{tabular}{c|c|c|c}
$ f $ & Вектор & Терм & $L(f)$ \\
\hline
$ 0 $ & $ (00) $ & $ 0 $ & $ 0 $ \\
$ x $ & $ (01) $ & $ x $ & $ 1 $ \\
$ \overline{x} $ & $ (10) $ & $ \overline{x} $ & $ 1 $ \\
$ 1 $ & $ (11) $ & $ 1 $ & $ 1 $ \\
\end{tabular}
\end{center}

На сегодняшний день единственным способом достоверного нахождения МПП (минимальное полиномиальное 
представление) является перебор.

Допустим, имеется функция $f(x_1, \ldots, x_n)$. Представим её через другие функции, вынеся один из аргументов:

\begin{equation}
  f(x_1, \ldots, x_n) = x_1 f_1(x_2, \ldots, x_n) \oplus \overline{x_1} f_2(x_2, \ldots, x_n) \oplus f_3(x_2, \ldots, x_n)
\end{equation}

Вся функция была поделена на три части: слагаемые с аргументом $x_1$, слагаемые с аргументом $\overline{x_1}$ и слагаемые без аргумента $x_1$.

Причем, $L(f) = L(f_1) + L(f_2) + L(f_3) $, что очевидно.

Итак, мы пришли к дедуктивному умозаключениюу, что для того чтобы найти сложность функции $f$ от $n$ аргументов, нам надо найти минимальные сложности функций $f_1$, $f_2$ и $f_3$ от $(n - 1)$ аргументов.

Подставив в это тождество вместо $x_1$ $0$ и $1$ получается следующая система уравнений: 

$$
\begin{cases}
f(0, \ldots, x_n) = f_2(x_2, \ldots, x_n) \oplus f_3(x_2, \ldots, x_n) \\
f(1, \ldots, x_n) = f_1(x_2, \ldots, x_n) \oplus f_3(x_2, \ldots, x_n) \\ 
\end{cases}
$$

Преобразовав эту систему к следующему виду, делаем вывод, что  $f_1$ и $f_2$ выражаются через $f_3$, $f_{x_1}^0$ и $f_{x_1}^1$:

$$
\begin{cases}
f_2(x_2, \ldots, x_n) = f(0, \ldots, x_n) \oplus f_3(x_2, \ldots, x_n) \\
f_1(x_2, \ldots, x_n) = f(1, \ldots, x_n) \oplus f_3(x_2, \ldots, x_n) \\ 
\end{cases}
$$

Получается, что для того, чтобы найти сложность функции $f$ от $n$ переменных достаточно перебрать все функции $f_3$  от $(n-1)$ переменных.

Исходя из этого и строится основной алгоритм. 

\begin{tabular}{l}

int $ min = -1$;\\
for($f_3 = 0; f_3 \le 2^{2^{n-1}} ; f_3++$) \{ \\
~~$ f_1 = f_{x_1}^1 \oplus f_3 $;\\
~~$ f_2 = f_{x_1}^0 \oplus f_3 $;\\
~~if ($min == -1 || min > L(f_1) + L(f_2) + L(f_3)$)\\
~~~~$min = L(f_1) + L(f_2) + L(f_3)$;\\
\}\\

\end{tabular}

В данном алгоритме находится минимальная сложность для функции $f$.
Подразумевается, что при нахождении сложности функции от $n$ переменных известны все сложности
функций от $(n - 1)$ переменных. Очевидно, что нахождение сложности одной функции от $n$ переменных 
по данному алгоритму будет выполнено за $C 2^{2^{n-1}} (C - const) $ операций.
Отсюда получается, что для нахождения сложностей полного класса функций от $n$ переменных будет выполнено
$ C_1 2^{2^{n}} C_2 2^{2^{n-1}} $ операций.

Ниже представлена таблица, на которой видно возрастание перебора при увеличении $n$
\begin{center}
\begin{tabular}{c|c|c|c}
$n$ & Функций & Сложность & Полный класс \\
\hline
1 & $2^{2}$ & $2^{1}$ & $2^{3}$ \\
2 & $2^{4}$ & $2^{2}$ & $2^{6}$ \\
3 & $2^{8}$ & $2^{4}$ & $2^{12}$ \\
4 & $2^{16}$ & $2^{8}$ & $2^{24}$\\
5 & $2^{32}$ & $2^{16}$ & $2^{48}$ \\
6 & $2^{64}$ & $2^{32}$ & $2^{96}$ \\
7 & $2^{128}$ & $2^{64}$ & $2^{192}$
\end{tabular}
\end{center}

При современных возможностях вычислительной техники при указанном выше алгоритме можно найти сложность
всех функций максимум от 5 переменных и при необходимости найти сложность какой-нибудь одной функции от 6 переменных.
Но эти вычисления будут быстрыми только в том случае, если использовать высокопроизводительный кластер с большим объемом 
памяти на узлах.

Эту же задачу можно решить на персональном компьютере, если убрать большинство функции, для которых есть эквивалентые (по сложности).

{\bf Алгоритм с использованием SP-эквивалентности}. В описании данного алгоритма мы используем функцию  {\tt найти\_минимальную\_сложность()}, 
которая представляет из себя алгоритм нахождения минимальной сложности для заданной функции. Функцию 
{\tt сложность\_не\_известна()} мы используем для определения был ли найден хоть один из представителей класса.
Функция {\tt сложность\_известна()} используется, чтобы определить класс функций как известный.

\begin{tabular}{l}

for($f = 0; f \le 2^{2^{n}} ; f++$) \{ \\
~~if ({\tt сложность\_не\_известна($f$)}) \{ \\
~~~~ {\tt найти\_минимальную\_сложность($f$)}; \\
~~~~ {\tt сложность\_известна($f$)}; \\
~~\} \\
\} \\

\end{tabular}

Булевы функции можно выделять в некоторые классы. Если использовать нижеописанные классы, то 
сложности функций в них будут одинаковыми. Класс можно хранить одним из представителей (например, минимального представителя)
и сложностью этого представителя. При необходимости можно будет "развернуть" класс из этого представителя.

{\bf Перестановки аргументов}. Есть функции $f$ и $g$, такие что
$$f(x_1, \ldots, x_i, x_j, \ldots, x_n) = g(x_1, \ldots, x_j, x_i, \ldots, x_n) \Rightarrow L(f) = L(g)$$ 

Перестановки аргументов находятся при помощи побитовых операций и масок переменных $n$-аргументной функции. В итоге
часть элементов вектора функции поменяется местами с другой частью, в следствии чего функция $f$ примет вид функции $g$.
Маски обозначаются $M_n^{x_i}$. Если взять две функции $f$ и $g$, такие что $f(x_1, \ldots, x_i, \ldots, x_j, \ldots, x_n) = g(x_1, \ldots, x_j, \ldots, x_i, \ldots, x_n)$.
И получить вектор $M_c = M_n^{x_i} \oplus M_n^{x_j} $, то
$$ 
f \ne g \Rightarrow
\begin{cases}
M_c \wedge f \ne M_c \wedge g \\ 
\overline{M_c} \wedge f = \overline{M_c} \wedge g
\end{cases}
$$

Теперь необходимо разделить маску $M_c$ на две (чтобы определить какие именно элементы вектора сдвигать):
$M_c^f = M_c \wedge M_n^{x_i}$ и $M_c^g = M_c \wedge \overline{M_n^{x_i}}$. 

Сдвиг вправо и влево равен, так как элементы вектора просто заменяются друг другом. Сдвиг обозначим через $t$.
$$
t = \left| 2^{\left| n-i-1 \right|} - 2^{\left| n-j-1 \right|} \right|
$$

Побитовые операции сдвига влево и вправо обозначим через $<<$ и $>>$, соответственно.

Итак, результатом перемены местами двух аргументов функции будет вектор, получаемый следующим образом:

$$
f \overline{M_c} \oplus (f  M_c^f >> t) \oplus (f M_c^g << t)
$$

Поскольку стояла задача перебрать все перестановки аргументов функции, то используется порядок перестановок получения 
каждой последующей из предыдущей сдвигом двух рядом стоящих. Чтобы экономить время выполнения 
в начале запуска программы находится массив этих перестановок, который уже в дальнейшем используется. Размер данного массива
равен $n!$.

{\bf Отрицания аргументов}. Есть функции $f$ и $g$, такие что

$$
f(x_1, \ldots, x_i, \ldots, x_n) = g(x_1, \ldots, \overline{x_i}, \ldots, x_n) \Rightarrow L(f) = L(g)
$$

Результатом отрицания $i$-го аргумента функции $f$ будет

$$
(f M_n^{x_i} >> 2^{n-i-1}) \oplus (f \overline{M_n^{x_i}} << 2^{n-i-1})
$$

Чтобы перебирать все отрицания функции необходимо использовать такой порядок отрицания аргументов, чтобы уменьшить 
количество вычислений. Поэтому отрицания аргументов ставятся по коду грея, массив значений которого обсчитывается заранее.
Его размер равен $2^n$.

{\bf Расширение отрицания аргументов (производными)}. Производной функции $f$ по аргументу $x_i$ будем называть 
$f_{x_i}^{'} = f_{x_i}^0 \oplus f_{x_i}^1$.

Выше были описаны следующие неравенства:

$$
  L(f) = L(\overline{x_i} f_{x_i}^{0} \oplus x_i f_{x_i}^{1})
       = L(\overline{x_i} f_{x_i}^{1} \oplus x_i f_{x_i}^{0})
$$


При помощи производных их можно расширить следующими равенствами:

$$
  L(f) = L(\overline{x_i} f_{x_i}^{0} \oplus x_i f_{x_i}^{'})
       = L(\overline{x_i} f_{x_i}^{'} \oplus x_i f_{x_i}^{0})
$$

$$
  L(f) = L(\overline{x_i} f_{x_i}^{1} \oplus x_i f_{x_i}^{'})
       = L(\overline{x_i} f_{x_i}^{'} \oplus x_i f_{x_i}^{1})
$$

Размер ($s$) класса SP-эквивалентности сокращает оценку сложности алгоритма в $s$ раз. Размер 
класса SP-эквивалентности равен $ n! \cdot 6^n $.

Если пренебречь временем затрачиваемым на определение класса функции, то таблица общей сложности алгоритма
в зависимости от количества аргументов функции
изменится следующим образом:

\begin{center}
\begin{tabular}{c|c|c}
$n$ & Без классов & lp-классы \\
\hline
1 & $8$ &  $ 2$ \\
2 & $64$ &  $ 3$ \\
3 & $4096$ &  $6$ \\
4 & $16777216$  & $30$\\
5 & $\approx 2 \cdot 10^{14}$ & $6936$\\
6 & $\approx 2 \cdot 10^{28}$ & $\approx 2 \cdot 10^{21} $ \\
7 & $\approx 2 \cdot 10^{56}$ & $\approx 4 \cdot 10^{48} $
\end{tabular}
\end{center}

Очевидно, что полностью функции можно найти только для функций от 5 переменных. Но, дальше можно
находить сложности любой функции от 6 переменных (используя все функции от 5 переменных). 
Следующая задача найти самые сложные функции. Для функций от $ 1 - 5 $ переменных их найти несложно, так как есть все 
функции. 

{\bf Общий вид алгоритма создания классов.} Для создания классов использовался следующий алгоритм:

\begin{tabular}{l}

forall($f \in B$) \{ \\
~~{\tt пометить\_весь\_класс($f$)} \\
~~{\tt убрать\_пометку\_с\_функции($f$)} \\
~~{\tt запомнить\_представителя\_класса($f$)} \\
\} \\

\end{tabular}

Функции 
{\tt убрать\_пометку\_с\_функции($f$)} и \\
{\tt запомнить\_представителя\_класса($f$)} являются достаточно тривиальными, и ниже я опишу функцию 
{\tt пометить\_весь\_класс($f$)}:

\begin{tabular}{l}

{\tt пометить\_весь\_класс($f$)} \{ \\
~~{\tt в\_очередь\_и\_пометить($f$)} \\
~~while({\tt очередь\_не\_пуста()}) \{ \\
~~~~$f_t$ = {\tt элемент\_из\_очереди()} \\
~~~~for($i = 0; i \leq n; i++$) \{ \\
~~~~~~{\tt в\_очередь\_и\_пометить(отрицание $i$ аргумента $f$)} \\
~~~~~~{\tt в\_очередь\_и\_пометить(производную (1) $i$ аргумента $f$)} \\
~~~~~~{\tt в\_очередь\_и\_пометить(производную (2) $i$ аргумента $f$)} \\
~~~~~~{\tt в\_очередь\_и\_пометить(производную (3) $i$ аргумента $f$)} \\
~~~~~~{\tt в\_очередь\_и\_пометить(производную (4) $i$ аргумента $f$)} \\
~~~~~~{\tt в\_очередь\_и\_пометить(перестановку $i$ аргумента $f$)} \\
~~~~\} \\
~~\} \\
\} \\

\end{tabular}

{\bf Понижение сложности функций от 7 переменных.}
Перед нами стоит задача попытаться понизить верхнюю оценку самой сложной функции от 7 переменных. 
Функцию от 7 переменных можно сложить из 2-х функций от 6 переменных. 

$$
f(x_1, \ldots, x_7) = x_1 f_1(x_2,\ldots,x_7) \oplus \overline{x_1} f_2(x_2,\ldots,x_7) 
$$

Отсюда можно сделать вывод:

$$
L(f) \leq L(f_1) + L(f_2)
$$

Получается, что если $L(f_1) = a$ и $L(f_2) = b$, то $L(f)$ не будет превышать $(a+b)$. 
Благодаря этому можно понижать сложность функций от 7 переменных путем "склеивания"  2-х функций определенной сложности от 6 переменных.

\begin{center}
\begin{tabular}{c|c|c}
Верхняя оценка & $L(f_1)$ & $L(f_2)$ \\
\hline
30 & $15$ &  $15$ \\ \hline
29 & $15$ &  $14$ \\
29 & $14$ &  $15$ \\ \hline
28 & $15$ &  $13$ \\
28 & $14$ &  $14$ \\
28 & $13$ &  $15$ \\ \hline
$\ldots$ & $\ldots$ &  $\ldots$ \\
\end{tabular}
\end{center}

Здесь используется следующий алгоритм:

\begin{tabular}{l}

forall($f_1 \in LP(B_a)$) \{ \\
~~forall($f_2 \in B_b$) \{\\
~~if ({\tt определение\_верхней\_оценки($f$)} $ \left \geq a+b$) \{ \\
~~~~ c = {\tt приблизительное\_нахождение\_сложности($f$)}; \\
~~~~ if ($c \geq a+b$) {\tt запомнить\_функцию($f$,c)}; \\
~~\} \\
\} \\

\end{tabular}

В указанном алгоритме используются следующие обозначения: 

\begin{enumerate}
\item $LP()$ - множество классов lp-эквивалентности, 
\item $B_i = \left \{ f(x_1,\ldots,x_n) | L(f) = i\right \}$,
\item {\tt определение\_верхней\_оценки($f$)} - быстрый алгоритм верхней оценки сложности,
\item {\tt приблизительное\_нахождение\_сложности($f$)} - эвристическй алгоритм более точной верхней оценки,
\item {\tt запомнить\_функцию($f$,c)} - запись в базу данных информацию о функции (бинарный файл).
\end{enumerate}

Итак, если на паре $(15,15)$ самая большая сложность будет $\alpha$ и $\alpha < 30$, то функций от 7 переменных сложности 30 не существует, а это значит, что верхняя оценка будет понижена до $ \alpha) $. Такое понижение сложности надо проделать для каждой пары $(a,b)$ до тех пор, пока $max(c, \alpha)$ не будет равно $c$, $c = \overline{ 1 \ldots 30}$. 

{\bf Поиск функций от 6 переменных, имеющих высокую сложность}. 
Этот поиск производится аналогично поиску для 7 переменных. Для задачи поиска функций от 6 переменных 
есть некоторый $a$, который меньше либо равен сложности находимых функций. В данный момент в алгоритме на MPI $a = 14$. 

Построим аналогичную таблицу:

\begin{center}
\begin{tabular}{c|c|c}
Верхняя оценка & $L(f_1)$ & $L(f_2)$ \\
\hline
18 & $9$ &  $9$ \\ \hline
17 & $9$ &  $8$ \\
17 & $8$ &  $9$ \\ \hline
16 & $9$ &  $7$ \\
16 & $8$ &  $8$ \\
16 & $7$ &  $9$ \\ \hline
15 & $9$ &  $6$ \\
15 & $8$ &  $7$ \\
15 & $7$ &  $8$ \\
15 & $6$ &  $9$ \\ \hline
14 & $9$ &  $5$ \\
14 & $8$ &  $6$ \\
14 & $7$ &  $7$ \\
14 & $6$ &  $8$ \\
14 & $5$ &  $9$ \\ \hline
$\ldots$ & $\ldots$ & $\ldots$ \\
\end{tabular}
\end{center}

Результатом работы программы для функций от 6 переменных появляются бинарные файлы, разделенные сложностями функций в них.

{\bf Генетический алгоритм.} Для оптимизиации поиска сложностей был сделан эвристический алгоритм, который достаточно точно дает верхнюю оценку сложности для выбранной функции за короткое время (Core 2 Duo 2200,2 GiB RAM, Ubuntu x64 <1 с.). 

Для генетического алгоритма был создан класс, в котором имеются методы относящиеся к сущности таких алгоритмов (генерация начальной популяции, скрещивание двух особей популяции, мутация одной особи популяции, ...).

Для разработки алгоритма было найдено 106 сложностей (эталонных) функций полным перебором. 
Для этого была написанна программа, с использованием pthreads. Она была запущена на 4-х
 процессорах. Эти вычисления заняли около 5 часов работы. Т.е. 10 минут на поиск сложности 
 одной функции на одном процессоре.

На эталонных функциях проверялись различные модификации генетического алгоритма и 
статистически определялась "правильность" выбранного направления модификации.

{\it Методы генерации начальной популяции.} Ниже приведены примеры начальных генераций и 
их названия (или регулярные выражения определяющие их).

\begin{enumerate}
\item $0^{*}10^{*}$ (0001, 0010, 0100, 1000) - 57,5%
\item $0^{*}1^{*}$ (0001, 0011, 0111, 1111) - 74,5%
\item $1^{*}0^{*}$ (1111, 1110, 1100, 1000) - 85,8%
\item Симметричные вектора, где левая половина представляется как $1^{*}0^{*}$ (1001, 1111, 0110, 0000) - 83,0%
\item Числа Фиибоначчи (1, 2, 3, 5, 8, ...) - 55,7%
\item Простые числа (1, 2, 3, 5, 7, 11, ...) - 48,1%
\item $0^{*}1^{n}0^{*}$ (0011...1, 0011...10,...) 
- для n = 1..31 (57.5472, 60.3774, 61.3208, 73.5849, 71.6981, 74.5283, 78.3019, 
81.1321, 78.3019, {\bf 82.0755}, 79.2453, 79.2453, 74.5283, 75.4717, 75.4717, 79.2453, 
{\bf 82.0755}, 81.1321, 80.1887, 79.2453, 80.1887, {\bf 82.0755}, 80.1887, 81.1321, 70.7547, 
60.3774, 44.3396, 50.9434, 16.9811, 19.8113, 15.0943) 
\end{enumerate}
   
{\it Методы мутации.} 

\begin{enumerate}
\item Побитовая мутация (0001, 0010, 0100, 1000) - 85,5%
\item Сложение с векторами (0001, 0011, 0111, 1111) - 78,3% 
\end{enumerate}

{\bf Оптимизация библиотеки от 5 переменных.} В нашей задаче приходится хранить 
функции от 5 переменных и их сложности. 
Для $n = 5$ количество функций $2^{2^5} = 4294967296$. Если сложности этих функций 
хранить в оперативной памяти, то это 4 GiB, а это технически сложно найти необходимое 
количество узлов с таким объемом оперативной памяти.

Поскольку сложности от 5 переменных варьируются в $\left [ 0 .. 9 \right ]$, т.е. 4 
бита иформации. То в один байт можно помещать информацию о 2-х функциях. Таким образом 
объем необходимой памяти можно понизить в два раза до 2 GiB.

Чтобы еще понизить объем используемой оперативной памяти пришлось частитчно воспользоваться классами эквивалентности. А точнее, были взяты функции из n-класса, которые получаются только по первому отрицанию. 

Была создана библиотека, значения из которой берутся следующим образом (подразумевается, 
что функция $f$ - минимальна в своем классе $n_{x_1}$):

\begin{enumerate}
\item $n$ - количество переменных
\item $f$ - функция, представленная в десятичном виде
\item $i$ - индекс в массиве библиотеки
\item $N = \left \lfloor {f \over 2^{2^{n-1}}+1} \right \rfloor$
\item $i = f - {(1 + N)N \over 2}$
\end{enumerate}
   
{\bf Понижение верхней оценки.} У нас в работе используется два способа понижения верхней оценки 
сложности функции. 

{\it Понижение верхней оценки по разложению Шеннона.} Для функций от 6 или 7 аргументов используется 
склеивание двух функций от меньшего на один числа аргументов. Это склеивание производится по разложению 
Шеннона. 

$$
f(x_1,\dots,x_n) = x_i f_1(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n) \oplus \overline{x_i} f_2(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n)
$$
   
Тут видно, что $L(f) \leq L(f_1) + L(f_2) $. 

{\it Понижение верхней оценки по склейкам.} Допустим, имеется функция $f$ c вектором 
($\alpha_1, \ldots, \alpha_{2^n}$). $ \sum_{i=1}^{2^n} \alpha_i = k$. Для данного вектора найдем совершенную полиномиальную нормальную форму (СПНФ).
В результате получится терм следующего вида:
$$
f(x_1, \ldots, x_n)  = 
(x_1^{\beta_{1,1}} \ldots x_n^{\beta_{n,1}}) \oplus  
(x_1^{\beta_{1,2}} \ldots x_n^{\beta_{n,2}}) \oplus  \ldots \oplus
(x_1^{\beta_{1,k}} \ldots x_n^{\beta_{n,k}})
$$

Многократно используя следующее правило:
$$
(x_1^{\gamma_1} x_2^{\gamma_2} \ldots x_i^{\gamma_i} \ldots x_n^{\gamma_n}) \oplus
(x_1^{\gamma_1} x_2^{\gamma_2} \ldots x_i^{\overline{\gamma_i}} \ldots x_n^{\gamma_n}) = 
(x_1^{\gamma_1} x_2^{\gamma_2} \ldots x_{i-1}^{\gamma_{i-1}}x_{i+1}^{\gamma_{i+1}} \ldots x_n^{\gamma_n})
$$

Приходим к терму, в котором сократилось количество слагаемых. Количество слагаемых полученного терма и является верхней оценкой.

Для реализации этого алгоритма был написан класс склейки и функция, которая производит все возможные склейки.

{\bf MPI приложение для поиска функций, которые составляют определнную сложность.} Для поиска функций самой высокой
 сложности от 6 и 7 аргументов было написано приложение для кластера с использованием технологии MPI.
 
 Данное приложение разделено на два типа узлов: серверный и клиентский. 
 
 Серверный узел раздает задания клиентским: функции. Клиентские узлы, получив задание, вычисляют сложность по
  генетическому алгоритму, а затем отправляют результат серверу, который в свою очередь определяет "полезность"
   вычисленной функции и заносит, при необходимости, ее в базу.
 
 Серверный узел управляет началом работы и прекращением. Клиент, запрашивая новое задание, может получить отказ,
  на что он прекращает работу. Эта ситуация может возникнуть, если приложение на сервере было терминировано или
   задания закончились.
 
 Если была произведена терминация сервера (командой kill в консоли linux), то он дожидается окончания заданий
  клиентами, отправляет им сообщение о прекращении работы, сохраняет текущее состояние работы и закрывается.

 {\bf Реализация.} Вся работа производится через систему контроля версий Subversion, хостинг которой предоставлен проектом code.google.com. На сайте этого же проекта имеется wiki-страница, которая пополняется подробностями реализации, текущими задачами или вопросами.
 
 В итоге было создано около 100 файлов: библиотеки функций, классы, cpp-файлы программ, файлы конфигураций и просто текстовые файлы. 
 
 Для реализации были созданы следующие заголовочные файлы:
 
 \begin{enumerate}
 	\item {\tt both.h} - файл общий для всех программ, в нем хранятся методя для модификации булевых функций (такие как отрицание по аргументу, перестановка аргументов, производные по аргументу и др.).
 	\item {\tt binfile.h} - файл, содержащий объявления типов Int8, Int32 и Int64 (целые беззнаковые типы с соответсвующими размерностями); класс для работы с бинарными файлами (этот класс с шаблонными методами упрощает чтение и запись в бинарные файлы).
 	\item {\tt timeelapsed.h} - класс, который считает время: от времени создания объекта до времени вывода на экран (создан оператор для работы с потоком вывода).
 	\item {\tt libn1.h} - файл, содержащий класс хранения библиотеки всех функций, но в sp-классе отрицаний 
 	по первому аргументу и с хранением в одном байте двух значений сложностей функций.
 	\item {\tt libn1\_plug.h} - класс-заглушка, который был сделан на процесс отладки, чтобы не загружать каждый раз  библиотеку размерм 1 GiB.
 	\item {\tt g6.h} - файл, содержащий в себе класс для эволюционного алгоритма и функции для работы с ним, а также функции полного перебора.
 	\item {\tt upperbound6v.cpp} - реализация MPI-приложения для поиска функций указанной сложности.
 	\item {\tt gluing\_min.cpp} - реализация понижения верхней оценки сложности через склейки.
 	\item {\tt gen1\_5classes.cpp} - реализация приложения, для вычисления классов эквивалентности.
 	\item {\tt g6gf.cpp} - приложение для нахождения сложности случайных функций полным перебором.
 	\item {\tt g6.cpp} - поиск сложности для функции от 6 аргументов.
 	\item {\tt f6\_etalon.txt} - набор эталонных функций от 6 аргументов.
 	\item {\tt 5lp.txt} - LP-классы для функций от 5 аргументов.
 \end{enumerate}

\mychap{Заключение}

Результатом нашей работы является реализация некоторых алгоритмов, с помощью которых можно найти минимальные 
полиномиальные представления булевых функций, часть вычисленных данных.

В дальнейшем можно продолжить изучение данной области, с целью нахождения 
самой сложной функции от 7 переменных, по алгоритму
аналогичному для нахождению сложности функций от 6 переменных. 



\end{document}
